The present invention relates to digital image processing and, more specifically, to the detection of edges in images, e.g., differentially encoded images.
As a result of image processing, edges are often introduced into images. Letterboxing of movies for display on television is an example of one form of image processing that introduces horizontal edges into images. In the case of letterboxing, black regions are added to the lower and upper portions of an image.
An example of letter boxing is shown in FIG. 1. As illustrated, a letterbox image 10 comprises upper and lower black borders 12, 12xe2x80x2 and a central image region 14. Horizontal edges 13, 13xe2x80x2 result from the transition from the black border regions 12, 12xe2x80x2 to the center image region 14. The horizontal edges 13, 13xe2x80x2 resulting from letter boxing are often strong edges due to the black nature of the border regions 12, 12xe2x80x2.
Various image processing operations require information about the presence of edges, such as those resulting from letterboxing, within an image.
One known edge detection technique, referred to as the gradient method is described in Digital Image Processing, by William K. Pratt (1991). The gradient method involves the computation of the first derivative of the pixel data. This usually involves calculating pixel differences from unencoded pixel values. This can involve a considerable number of processing operations.
Accordingly, the known gradient method edge detection technique suffers from the disadvantage of requiring a substantial amount of image processing to detect edges in an image. Furthermore, the known edge detection technique normally involves the use of unencoded, e.g., uncompressed, image data. Accordingly, in order to detect an edge in an encoded image, the image normally needs to be completely decoded prior to detecting edges within the image.
For data storage and transmission purposes, images are normally encoded, e.g., compressed, to reduce the amount of data used to represent an image. Prior to use, e.g., subsequent image processing and/or display, encoded images are normally decoded.
Differential coding of discrete cosine transform coefficients (DCTs) is used in a wide variety of image encoding schemes including, e.g., the international video standard. MPEG-2 (ISO/IEC 13818-2). MPEG-2 has been used as the basis for several commercial applications including digital video disks (DVD) and digital broadcast television.
In accordance with MPEG-2, pixels are normally grouped into blocks for encoding purposes. The term block is used in the present application to refer to luminance (luma) blocks. Each block corresponds to 16 pixels. There are four blocks per macroblock. FIG. 2 illustrates the relationship of the four luma blocks (0, 1, 2, 3) of a macroblock 20.
In MPEG-2, the slice syntax element is used to encapsulate data used to decode individual macroblocks. Multiple slices may exist in a given macroblock row of an image, however a slice cannot span across rows of macroblocks. The slice syntax element also carries the slice_vertical_position which provides information about the vertical position of the macroblock data. The vertical position is measured in macroblock units from the top of the picture. MPEG-2 requires that all the slices that may be present in a given row of macroblocks carry the same slice_vertical_position value. The value of the slice_vertical_position may be used to determine when the macroblock data corresponding to a given row of macroblocks has been fully observed. This is done by noting when the value of the slice_vertical_position increases by one unit.
FIG. 3 illustrates an image segment 30 corresponding to an upper portion of the image 10. In FIG. 3, a horizontal row of macroblocks corresponding to, e.g., a slice 31, is shown passing through the horizontal edge 13.
In the slice 31, first and second blocks of each macroblock have similar luminance characteristics because they both correspond to the black border region 12. In addition, the third and fourth blocks of each macroblock have similar luminance characteristics because they both correspond to the center image region 14. However, it can be seen that, for each macroblock 32, 33, 34, 35, 36, the upper two blocks (blocks 0, 1) will have a DC level that is noticeably different from that of the lower two blocks (blocks 2, 3) since there is a large, difference in the luminance characteristics of the upper and lower blocks. It is this difference in luminance characteristics which is responsible for the presence of the horizontal edge 13.
As part of the MPEG-2 encoding process, discrete cosine transform encoding is performed on image data to produce a plurality of discrete cosine transform (DCT) coefficients. In order to reduce the amount of data used to represent the encoded images, DC DCT coefficients are frequently represented as differential values, i.e., values which indicate the difference from a preceding DC DCT coefficient value. Such a differential value is described in the MPEG-2 specification as a dc_dct_differential.
Thus, in MPEG-2, the DC components of blocks of intra-coded macroblocks are encoded differentially across a slice. This takes advantage of the fact that the DC level of a picture does not ordinarily exhibit sharp changes across small regions. By differentially encoding the DC coefficients, it is possible, in the mean, to obtain a certain degree of data compression.
FIG. 4 shows how MPEG-2 differential encoding proceeds throughout the blocks 32, 33 in the slice 31 of macroblocks. For the very first macroblock 32 in a slice, the DCT DC predictors are reset. Thus, the first block, block 0, is differentially coded using a preceding DC DCT value of 0 to generate the dc_dct_differential. The effect of coding the first block of a slice in this manner is the same as performing non-differential coding since the coding does not use an actual preceding DC DCT coefficient value. By restarting the differential coding with the first block of each slice, the propagation of errors is reduced at the expense of having to explicitly encode the first DC DCT coefficient of a slice. After the first block of the first macroblock of a slice, the DCT DC coefficients are differentially encoded using a preceding DC DCT coefficient in the slice as a reference value.
Since the macroblock 32 is the first macroblock in slice 31, the dc_dct_differential for block 0 will correspond to the actual DC DCT value for this block. The DC DCT for block 1 of the first macroblock 32 is differentially coded using the DC DCT value of block 0 as the predictor. Considering the edge shown in FIG. 1 there is uniformity between the DC DCT values of blocks 0 and 1 so the dc_dct_differential for block 1 will be small.
In the case of block 2 of macroblock 32, the DC DCT will be differentially coded using the DC DCT value of block 1 as the predictor. When there is uniformity between the DC value of the blocks, the dc_dct_differential is expected to be small. However, a large dc_dct_differential is expected when a horizontal edge is present.
Considering FIG. 3 as an example, it will be seen that when a horizontal edge is present there is a large difference in the DC levels of blocks 1 and 2 due to the horizontal edge 13. This results in a dc_dct_differential for block 2 which will be large compared to that for block 1.
When differentially coding block 3, the DC DCT value of block 2 of the same macroblock is used as the predictor. In the FIG. 3 example, the differential for block 3 of the first macroblock 32 will be small. This is because the differences in the DC levels of blocks 2 and 3 of macroblock 32 are small or non-existent. After coding the DC DCT values for block 3, encoding of the first macroblock is finished.
To differentially encode the first block of a macroblock, which is not the first macroblock of a slice, the DC DCT value of block 3 of the previous macroblock is used as the predictor. The dc_dct_differentials for the remaining blocks of the macroblock are coded using the DC DCT of the preceding block as the predictor. When the image is uniform throughout a region, the dc_dct_differentials will be small. However, when sharp edges are present this will not be the case.
In the FIG. 3 example, it can be seen that there is a large difference in the DC DCT levels of block 3 of the first macroblock 32 and block 0 of the second macroblock 33. In fact, the dc_dct_differential will have the opposite sign to the dc_dct_differential for block 2 of the first macroblock 32. Considering the FIG. 3 example further, it will be seen that the dc_dct_differential for block 1 will be relatively small, while the dc_dct_differential for block 2 will be large and opposite in magnitude to that of block 0. The dc_dct_differential for block 3 of macroblock 33 should be small. A similar pattern of alternating small and large dc_dct_differential values will occur for the remaining macroblocks 34, 35 and 36 of exemplary slice 31 due to the existence of horizontal edge 13.
The differential encoding of the macroblocks in a slice proceeds as described above for subsequent macroblocks in a slice. At the start of the next slice, the predictors are reset and the process is repeated for the entire length of the picture, e.g., image, being coded.
The MPEG-2 video standard describes in detail the processes involved in decoding a video bitstream that is compliant with its syntax. As part of the video decoding process, the dc_dct_differential values are extracted from the encoded bitstream and are used to generate decoded image data. Accordingly, the dc_dct_differentials are readily obtainable from an encoded MPEG-2 bitstream and may be obtained without having to fully decode the encoded picture.
Information about the presence of edges can be used by a video decoder to control various aspects of the decoding process. It can also be used to control various image processing operations performed on decoded image data.
Given the use of encoding to store and transmit image data, the ability to detect edges within images without first having to fully decode encoded image data used to represent the images is desirable. Accordingly, there is a need for methods and apparatus that can detect edges within images represented by encoded image data.
From a processing efficiency perspective, there is also a need for methods and apparatus for detecting edges, which are less processor intensive than the known gradient technique described above. Accordingly, there is also a need for new edge detection techniques that can be used to detect edges in a manner that is efficient from a processing and/or implementation perspective.
The present invention is directed to methods and apparatus for detecting edges within images, e.g., in images represented by encoded image data.
In accordance with the present invention, dc_dct_differentials included in encoded image data are examined to determine the presence of an edge within an image portion, e.g., row or column, to which the examined dc_dct_differential data corresponds.
To identify horizontal edges in an image, dc_dct_differential data corresponding to a row of macroblocks is examined. In various horizontal edge detection embodiments, the dc_dct_differential data corresponding to differentials between vertically displaced blocks is extracted from an encoded bitstream and processed to detect horizontal edges. Thus, when detecting horizontal edges all or some dc_dct_differentials corresponding to horizontally displaced blocks are ignored, e.g., discarded, and the differentials corresponding to vertically displaced blocks are examined to detect horizontal edges. In some embodiments, the dc_dct_differential corresponding to the first block of the first macroblock in a slice is also ignored, e.g., discarded, since it is not differentially coded based on an actual preceding DC DCT image value.
To identify vertical edges in an image, dc_dct_differential data corresponding to a column of macroblocks is examined. In various vertical edge detection embodiments, the dc_dct_differential data corresponding to horizontally displaced blocks is extracted from an encoded bitstream. Thus, when detecting vertical edges all or some dc_dct_differentials corresponding to vertically displaced blocks are ignored, e.g., discarded, and the differentials corresponding to blocks which are displaced within an image horizontally but not vertically are examined to detect vertical edges.
Examination of dc_dct_differential data to detect edges includes performing an analysis operation, which may include, e.g., one or more filtering operations, and one or more threshold comparison tests.
In a first exemplary embodiment, dc_dct_differential data being examined to detect an edge is filtered using, e.g., a moving average filter, and the filter output is compared to a threshold. When the threshold is exceeded, an edge is declared present in the image portion represented by the row or column of macroblock data being examined.
In other embodiments, dc_dct_differential data being examined to detect an edge is filtered using, e.g., a filter which detects the occurrence of consecutive dc_dct_differential values each of which exceeds a threshold, e.g., a threshold which is determined as a function of a preceding dc_dct_differential value. An edge is declared present if a threshold number of dc_dct_differentials satisfying the threshold and the consecutive occurrence requirement are detected.
To further refine the edge detection process, in some embodiments a fixed number of consecutive dc_dct_differentials exceeding the threshold discussed above, must be detected before an accumulated count of such events is incremented. The accumulated count is the value that is compared to the ultimate edge detection threshold that is used to determine if an edge is present.
The methods and apparatus of the present invention have the advantage over other systems of being able to detect the presence of an edge within a row or column of encoded image data without the need to fully decode the data in order to detect the presence or absence of an edge. In addition, the edge detection techniques of the present invention are relatively easy to implement and are less processor intensive than the known gradient technique of detecting edges.
Various additional features and advantages of the present invention will be apparent from the detailed description which follows.